/**
 * 排序法
 */
function majorityElement(nums: number[]): number {
  nums.sort((a, b) => a - b)
  return nums[Math.floor(nums.length / 2)]
}

/**
 * 哈希法
 */
function majorityElement2(nums: number[]): number {
  const counts: number[] = []
  let majorty = 0
  let count = 0
  nums.forEach(item => {
    if (counts[item]) {
      counts[item]++
    } else {
      counts[item] = 1
    }
    if (counts[item] > count) {
      count = counts[item]
      majorty = item
    }
  })
  return majorty
}

/**
 * 随机法
 * 记忆概率 大于一半选中 最快时间复杂度 O（n）
 */
/**
 * 分治法
 * 若为众数，那么它的对半分 也至少有一个是众数
 * 两个半边 计数更多的 众数 为整个的众数
 */
function majorityElement3(nums: number[]): number {
  
}

/**
 * Boyer-Moore 投票算法
 * 不同的数相消，最后剩下必然是众数
 * 实际操作 记录候选众数 和计数 相同不同减
 */